In digital signal processing, electrical signals are represented by a sequence of binary signals that are to be processed. A major part of this digital processing is done by digital filtering. A binary or digital input signal is put through a digital filter structure that alters the input signal according to its particular filter transfer function and is output as a desired output signal. For instance, a low-pass filter reduces the bandwidth of an input signal.
In most of the cases, the signals in digital signal processing represent time-dependent processes. An input signal x(t) is converted into an output signal y(t) by a filter system which is characterized by its pulse response h(t) or its transfer function, wherein both functions are connected through a Laplace transform: H(p)=L[h(p)]. A time-dependent input signal x(t) and the filter output signal y(t) are obtained from the convolution integral of the input signal x(t) with the filter pulse response h(t):
                              y          ⁡                      (            t            )                          =                                            x              ⁡                              (                t                )                                      *                          h              ⁡                              (                t                )                                              =                                    ∫                              τ                =                                  -                  ∞                                            t                        ⁢                                          x                ⁡                                  (                                      t                    -                    τ                                    )                                            ⁢                              h                ⁡                                  (                  τ                  )                                            ⁢                                                          ⁢                                                ⅆ                  τ                                .                                                                        (                  eq          .                                          ⁢          1                )            digital signal processing usually occurs in discrete time steps given by a clock signal, i.e. the values of the time-dependent signals and pulse response are only known at the times tn, and equation 1 reads:
                              y          ⁡                      (                          t              n                        )                          =                                            x              ⁡                              (                                  t                  n                                )                                      *                          h              ⁡                              (                                  t                  n                                )                                              =                                    ∫                              τ                =                                  -                  ∞                                                            t                n                                      ⁢                                          x                ⁡                                  (                                                            t                      n                                        -                    τ                                    )                                            ⁢                              h                ⁡                                  (                  τ                  )                                            ⁢                                                          ⁢                                                ⅆ                  τ                                .                                                                        (                  eq          .                                          ⁢          2                )            Calculating such a convolution integral in the time domain is very elaborate and time-consuming, because the integral has to be approximated by a discrete sum over a number N of samples of the integrand multiplied by the sampling interval. The number of samples N in the integration interval determines the accuracy of the evaluation. The number of complex multiplications that are required for N samples is proportional to N2.
Methods are known to reduce the order of O(N2) to O(N·lnN) by using a Fast Fourier Transform. This is described in Numerical Recipes in C: The Art of Scientific Computing, Vol. 8, Press, 2nd Edition, Cambridge University Press, 1992. Discrete Fast Fourier Transformation means that the calculations for the convolution are done in the frequency domain and then transformed back into the time domain for obtaining the output signal y(tn). However, it is favorable to solve the time-dependent problem posed by eq. 2 also in the time domain thereby reducing the amount of calculation force and hence increasing the speed of a digital filter.
Therefore, it is an object of the invention to provide a fast method and filter arrangement for digital filtering an input signal x(tn) in the time domain that requires a calculational effort which is lower than of the order O(N·lnN).